/*
 * @lc app=leetcode.cn id=15 lang=cpp
 *
 * [15] 三数之和
 *
 * https://leetcode-cn.com/problems/3sum/description/
 *
 * algorithms
 * Medium (34.83%)
 * Likes:    4517
 * Dislikes: 0
 * Total Accepted:    867.8K
 * Total Submissions: 2.5M
 * Testcase Example:  '[-1,0,1,2,-1,-4]'
 *
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0
 * 且不重复的三元组。
 * 
 * 注意：答案中不可以包含重复的三元组。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = []
 * 输出：[]
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：nums = [0]
 * 输出：[]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 0 
 * -10^5 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // vector<vector<int>> res;
        // sort(nums.begin(), nums.end());

        // for (int i = 0; i < nums.size(); i++){

        //     //这个判断的返回 应该是res,而不是{}，
        //     //本意是 当i往后移的时候，当出现nums[i]>0，即i之后的值就不需要在进行判断了
        //     //而不是说只判断i=0的情况，这样的话，一旦出现nums[i]>0的情况，就只能返回{}了，这样理解是错的
        //     if(nums[i] > 0 || nums.size() < 3) return res;

        //     //当i前进之后，应该向后判断是否重复，而不应该向前判断
        //     if(i > 0 && nums[i] == nums[i-1]) continue;

        //     //两个左右指针
        //     int left = i + 1;
        //     int right = nums.size() - 1;

        //     while(right > left){
        //         if(nums[i] + nums[left] + nums[right] > 0){
        //             //这种情况下，是因为和大了，说明right需要往左移动
        //             right--;
        //             //去重复操作，right左移之后还是和right位置上的值相等，继续左移
        //             while(right > left && nums[right] == nums[right + 1]) right--;
        //         } else if (nums[i] + nums[left] + nums[right] < 0) {
        //             //这种情况下，是因为和小了，说明left需要往右移动
        //             left++;
        //             //去重复操作，left右移之后还是和left位置上的值相等，继续右移
        //             while(right > left && nums[left] == nums[left - 1]) left++;
        //         } else {
        //             //找到了，则把这一组结果push_back进去res,
        //             res.push_back(vector<int>{nums[i], nums[left], nums[right]});

        //             //去重复操作
        //             while(right > left && nums[right] == nums[--right]);
        //             while(right > left && nums[left] == nums[++left]);

        //             //与上述两行同样目的，
        //             // while(right > left && nums[right] == nums[right - 1]) right--;
        //             // while(right > left && nums[left] == nums[left+1]) left++;
        //             // right--;
        //             // left++;
        //         }
        //     }
        // }
        // return res;

        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i++){

            if(nums[i] > 0) return res;
            if(i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;
            int right = nums.size() - 1;

            while(right > left){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                    while(right > left && nums[right] == nums[right+1]) right--;
                } else if (nums[i] + nums[left] + nums[right] < 0){
                    left++;
                    while(right > left && nums[left] == nums[left-1]) left++;
                } else {
                    cout<<i<<endl;
                    res.push_back(vector<int>{nums[i], nums[left], nums[right]});

                    while(right > left && nums[right] == nums[--right]);
                    while(right > left && nums[left] == nums[++left]);
                    // while(right > left && nums[right] == nums[right - 1]) right--;
                    // while(right > left && nums[left] == nums[left+1]) left++;
                    // right--;
                    // left++;              
                }
            }
        } 
        return res;

    }
};
// @lc code=end

